#include "MatrixGraph.h"

/**
 * 邻接矩阵创建无向图
 * 无向图的特点:
 *  1. 无向图的邻接矩阵是对称的
 *  2. 顶点 i 的度 = 第 i 行(列)中 1 的个数
 *
 * @param G
 * @return 0(error) | 1(ok)
 */
Status CreateUDG(ArrayMatrixGraph *G) {
    int i, j;
    /* 设置当前创建图的类型为无向图*/
    G->kind = UDG;

    printf("请输入无向图的顶点数: ");
    scanf("%d", &G->verTexCount);
    printf("请输入边的数量: ");
    scanf("%d", &G->arcCount);
    printf("依次输入顶点信息\n");
    for (i = 0; i < G->verTexCount; i++) {
        /* 分配空间 */
        G->verTexs[i] = (VerTexDataType) malloc(sizeof(char) * 10);
        printf("顶点: ");
        /* %s 输入不用加 & */
        scanf("%s", G->verTexs[i]);
    } /* for end */

    /* 初始化邻接矩阵,所有边的权值设置为 0 */
    for (i = 0; i < G->verTexCount; i++) {
        for (j = 0; j < G->verTexCount; j++) {
            G->arcs[i][j] = 0;
        } /* inner for end */
    } /* out for end */

    printf("请输入顶点和临界顶点信息,构建邻接矩阵\n");
    for (i = 0; i < G->verTexCount; i++) {
        /* 临时接受字符变量 */
        VerTexDataType tempVex1 = (VerTexDataType) malloc(sizeof(char) * 10);
        VerTexDataType tempVex2 = (VerTexDataType) malloc(sizeof(char) * 10);
        printf("顶点: ");
        scanf("%s", tempVex1);
        printf("邻接点: ");
        scanf("%s", tempVex2);

        /* 分别获得两个顶点在顶点数组中的坐标 */
        int x = LocateVex(G, tempVex1);
        int y = LocateVex(G, tempVex2);
        if (x == -1 || y == -1) {
            return ERROR;
        }
        /* 无向图的邻接矩阵是对称的 */
        G->arcs[x][y] = 1;
        G->arcs[y][x] = 1;

        /* 释放资源 */
        free(tempVex1);
        free(tempVex2);
    }
    return OK;
}

/**
 * 有向图:
 *  特点:
 *      1. 有向图的邻接矩阵可能是不对称的
 *      2. 顶点的出度 = 第 i 行元素之和
 *         顶点的入度 = 第 i 列元素之和
 *         顶点的度 - 第 i 行元素之和 + 第 i 列元素之和
 *   说明(有向图的邻接矩阵):
 *      第 i 行含义: 以节点 v_i 为尾的弧(出度边)
 *      第 i 列含义: 以节点 v_i 为为的弧(入度边)
 *
 * @param G
 * @return
 */
Status CreateDG(ArrayMatrixGraph *G) {
    int i, j;
    /* 设置当前创建图的类型为有向图*/
    G->kind = DG;

    printf("请输入有向图的顶点数: ");
    scanf("%d", &G->verTexCount);
    printf("请输入边的数量: ");
    scanf("%d", &G->arcCount);
    printf("依次输入顶点信息\n");
    for (i = 0; i < G->verTexCount; i++) {
        /* 分配空间 */
        G->verTexs[i] = (VerTexDataType) malloc(sizeof(char) * 10);
        printf("顶点: ");
        /* %s 输入不用加 & */
        scanf("%s", G->verTexs[i]);
    } /* for end */

    /* 初始化邻接矩阵,所有边的权值设置为 0 */
    for (i = 0; i < G->verTexCount; i++) {
        for (j = 0; j < G->verTexCount; j++) {
            G->arcs[i][j] = 0;
        } /* inner for end */
    } /* out for end */

    printf("请输入顶点和临界顶点信息,构建邻接矩阵\n");
    for (i = 0; i < G->verTexCount; i++) {
        /* 临时接受字符变量 */
        VerTexDataType tempVex1 = (VerTexDataType) malloc(sizeof(char) * 10);
        VerTexDataType tempVex2 = (VerTexDataType) malloc(sizeof(char) * 10);
        printf("顶点: ");
        scanf("%s", tempVex1);
        printf("邻接点: ");
        scanf("%s", tempVex2);

        /* 分别获得两个顶点在顶点数组中的坐标 */
        int x = LocateVex(G, tempVex1);
        int y = LocateVex(G, tempVex2);
        if (x == -1 || y == -1) {
            return ERROR;
        }
        /* 无向图的邻接矩阵是对称的 */
        G->arcs[x][y] = 1;
        /*
         * 有向图的邻接矩阵可能不对称
         * G->arcs[y][x] = 1;
         * */

        /* 释放资源 */
        free(tempVex1);
        free(tempVex2);
    }

    return OK;
}

/**
 * 返回某个定点在顶点集合中的下标(从 0 开始),不存在返回 -1
 * @param G
 * @param vex
 * @return
 */
int LocateVex(ArrayMatrixGraph *G, VerTexDataType vex) {
    int index = 0;

    /* 下标小于顶点个数进行循环 */
    while (index < G->verTexCount) {
        if (strcmp(G->verTexs[index], vex) == 0) {
            break;
        }
        index++;
    }
    return index == G->verTexCount ? -1 : index;
}

/**
 * 创建有向网
 * @param G
 * @return
 */
Status CreateDN(ArrayMatrixGraph *G) {
    int i, j;
    /* 设置当前创建图的类型为有向图*/
    G->kind = DN;

    printf("请输入有向网的顶点数: ");
    scanf("%d", &G->verTexCount);
    printf("请输入边的数量: ");
    scanf("%d", &G->arcCount);
    printf("依次输入顶点信息\n");
    for (i = 0; i < G->verTexCount; i++) {
        /* 分配空间 */
        G->verTexs[i] = (VerTexDataType) malloc(sizeof(char) * 10);
        printf("顶点: ");
        /* %s 输入不用加 & */
        scanf("%s", G->verTexs[i]);
    } /* for end */

    /* 初始化邻接矩阵,所有边的权值设置为 0 */
    for (i = 0; i < G->verTexCount; i++) {
        for (j = 0; j < G->verTexCount; j++) {
            G->arcs[i][j] = INT_MAX;
        } /* inner for end */
    } /* out for end */

    printf("请输入顶点和临界顶点信息,构建邻接矩阵\n");
    for (i = 0; i < G->verTexCount; i++) {
        /* 临时接受字符变量 */
        VerTexDataType tempVex1 = (VerTexDataType) malloc(sizeof(char) * 10);
        VerTexDataType tempVex2 = (VerTexDataType) malloc(sizeof(char) * 10);
        printf("顶点: ");
        scanf("%s", tempVex1);
        printf("邻接点: ");
        scanf("%s", tempVex2);

        /* 分别获得两个顶点在顶点数组中的坐标 */
        int x = LocateVex(G, tempVex1);
        int y = LocateVex(G, tempVex2);
        if (x == -1 || y == -1) {
            return ERROR;
        }
        int value;
        printf("请输入权值: ");
        scanf("%d", &value);
        /* 无向图的邻接矩阵是对称的 */
        G->arcs[x][y] = value;
        /*
         * 有向图的邻接矩阵可能不对称
         * G->arcs[y][x] = 1;
         * */

        /* 释放资源 */
        free(tempVex1);
        free(tempVex2);
    }

    return OK;
}


/**
 * 测试无向图
 */
void TestMatrixGraph() {
    ArrayMatrixGraph G;
    /* 创建无向图 */
    // Status status = CreateUDG(&G);

    // 创建有向图
    // Status status = CreateDG(&G);

    // 创建有向网
    Status status = CreateUDG(&G);
    if (status == ERROR) {
        printf("创建失败,请检查后重试!\n");
        return;
    }
    /* 打印邻接矩阵 */
    PrintGraph(G);
}


void PrintGraph(ArrayMatrixGraph G) {
    printf("打印图的邻接矩阵: \n");
    printf("\t");
    for (int i = 0; i < G.verTexCount; i++) {
        /* 输出顶点数组元素 */
        printf("\t%s", G.verTexs[i]);
    }
    printf("\n");
    for (int i = 0; i < G.verTexCount; i++) {
        printf("\t%s", G.verTexs[i]);
        for (int j = 0; j < G.verTexCount; j++) {
            if (G.arcs[i][j] == INT_MAX) {
                printf("\t∞");
            } else
                /* 输出邻接矩阵表示 */
                printf("\t%d", G.arcs[i][j]);
        }
        printf("\n");
    }
}
